#include<stdio.h>
#include<string>
#define MAX_LENGTH 10
using namespace std;
void get_next(string T,int next[]){
    int j=0,k=-1;
    next[0]=-1;//next[0]默认-1，next[1]默认0(下标从0开始)
    while(j<T.length()){
        //需要判断新加入的字符会不会影响最长相同前后缀
        if(k==-1||T[k]==T[j]){
            j++;
            k++;
            next[j]=k;//next[j+1]=k+1,因为在此之前T[0]...T[k]==T[j-k]...T[j](最长相同前后缀)
        }else{
            k=next[k];
            /*
                T[0]...T[k-1]T[k]T[k+1]...T[j-k]...T[j-1]T[j] T[j+1]
                此时T[j]!=T[k],所以就有 next[j+1] < k，那么求 next[j+1] 就等同于求 t[j] 往前小于 k 个的字符（包括t[j]）与 t[k] 前面的字符的最长相同前后缀，
                即 t[j-k+1] ~ t[j] 与 t[0] ~ t[k-1] 的最长重合串，那么就相当于求 next[k]
                （只不过 t[k] 变成了 t[j],但是 next[k] 的值与 t[k] 无关）!!!。所以才有了这句 k = next[k]，如果新的一轮循环（这时 k = next[k] ，j 不变）中 t[j] 依然不等于 t[k] ，则说明倒数第二大 t[0~next[k]-1] 也不行，那么 k 会继续被 next[k] 赋值（这就是所谓的 k 回退…），直到找到符合重合的子串或者 k == -1。
           */
        }
    }
}
void get_nextval(string t,int nextval[]){
    int next[MAX_LENGTH];
    get_next(t,next);
    int j=0,k=-1;
    while(j<t.length()){
        if(k==-1||t[k]==t[j]){
            j++;
            k++;
            if(t[j]==t[next[j]])
                nextval[j]=next[next[j]];
            else    
                nextval[j]=next[j];
        }
        k=nextval[k];
    }
}
int kmp_next(string S,string T){
    int next[MAX_LENGTH];
    get_next(T,next);
    int i=0,j=-1;
    while(i<S.length() && j<(int)T.length()){//返回类型是size_t，可以简单地认为是unsigned int类型，一定要化成有符号数才可以和有符号数比较大小
        if(j==-1 || S[i]==T[j]){
            i++;
            j++;
        }else{
            j=next[j];
        }
    }
    if(j>=T.length())   
        return i-T.length();
    else    
        return -1;
}
int common_matching(string S,string T){
    int i=0,j=0;
    while(i<S.length() && j<T.length()){
        if(S[i]==T[j]){
            i++;
            j++;
        }else{
            i=i-(j+1)+2;//表示当前第一个开始匹配主串的起始位置前一个位置，再加2就表示起始位置后一个位置
            j=0;
        }
    }   
    if(j>=T.length())   
        return i-T.length();
    else    
        return -1;
}
int main(){
    string S="abcabccbbdacdd";
    string T="ccbbd";
    printf("\n%d ",common_matching(S,T));
    printf("\n%d ",kmp_next(S,T));
    return 0;
}